package main

import (
	"sort"
)

var _ = `
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。


提示：

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
`

func mergeV2(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] <= intervals[j][0]
	})

	m := make(map[int]int)

	for _, interval := range intervals {
		isMatch := false

		delKeys := make([]int, 0)
		for start, end := range m {
			// 对比是否match
			isMatch = interval[0] > start || interval[1] <= end

			if isMatch {
				if start > interval[0] {
					delKeys = append(delKeys, start)
				}

				m[min(start, interval[0])] = max(end, interval[1])
			}
		}
		for k, _ := range delKeys {
			delete(m, k)
		}
		if !isMatch {
			m[interval[0]] = interval[1]
		}
	}
	res := make([][]int, 0)
	for start, end := range m {
		res = append(res, []int{start, end})
	}
	return res
}

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	res := make([][]int, 0)

	for i := 0; i < len(intervals); {
		start := intervals[i][0]
		end := intervals[i][1]

		j := i + 1
		for ; j < len(intervals); j++ {
			if intervals[j][0] <= end {
				// 区间右端点取最大值
				end = max(end, intervals[j][1])
			} else {
				break
			}
		}
		res = append(res, []int{start, end})
		i = j
	}

	return res
}

func main() {

}
